import java.util.*;
//实现求平方根 1.0
//public class Solution {
//    /**
//     *
//     * @param x int整型
//     * @return int整型
//     */
//    public int sqrt (int x) {
//        // write code here
//        if(x<0) return 0;
//        int left=1;int right=x;
//        while(true){
//            int mid=(left+right)>>1;
//            if(mid*mid==x){
//                return (int)mid;//强转
//            }
//            //？？？怎么向下取整
//            else if(mid*mid<x){
//                mid=mid+1;
//                if(mid*mid>x) return mid-1;
//            }else{
//                mid=mid-1;
//                if(mid*mid<x) return mid;
//            }
//        }
//    }
//
//    public static void main(String[] args) {
//        Solution solution=new Solution();
//        int x=solution.sqrt(2);
//        System.out.println(x);
//    }
//}


//？？？如果 mid*mid <=x 且(mid+1)(mid+1) <x 返回mid


public class Solution {
    /**
     *
     * @param x int整型
     * @return int整型
     */
    public int sqrt (int x) {
        if(x<0) return 0;
        int left=0;int right=x;int mid=-1;
        while(left<=right){
            mid=left+(left+right)>>2;
            if(mid<=x/mid && (mid+1)>x/(mid+1)){
                return (int)mid;
            }else if(mid>x/mid){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return (int)mid;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        int x=solution.sqrt(16);
        System.out.println(x);
    }
}
